#include<iostream>
using namespace std;
void paixu1(int a[], int n)  //冒泡排序的降序排序(时间复杂度为O(N^2))
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0 ; j < n-1; j++)
		{
			if (a[j] < a[j+1])
			{
				int temp = a[j + 1];
				a[j + 1] = a[j];
				a[j] = temp;
			}
		}

	}
}



int test01(int data[], int n)//遍历整个数组，求出数组中数据最大的数是几位数（d）
{
	int d = 1; //保存最大的位数
	int p = 10;
	for (int i = 0; i < n; ++i)
	{
		while (data[i] >= p)
		{
			p *= 10;
			++d;
		}
	}
	return d;
}
void paixu2(int arr[], int n) //基数排序
{
	int d = test01(arr, n);
	int temp[5];
	int count[10]; //计数器
	int i, j, k;
	int l = 1;
	for (i = 1; i <= d; i++) //进行d次排序(d不可能很大，所以这里的时间复杂度为o(1))
	{
		for (j = 0; j < 10; j++)
			count[j] = 0; //每次分配前清空计数器
		for (j = 0; j < n; j++)
		{
			k = (arr[j] / l) % 10; //统计每个桶中的记录数
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
		{
			k = (arr[j] / l) % 10;
			temp[count[k] - 1] = arr[j];
			count[k]--;
		}
		for (j = 0; j < n; j++) //将临时数组的内容复制到data中
			arr[j] = temp[j];
		l = l * 10;
	}
}


int main()
{
	//降序冒泡排序
	int a[5] = { 1,30,11,22,18 };
	int n = sizeof(a) / sizeof(a[0]);
	cout << "冒泡排序前的数组为：";
	for (int i = 0; i < n; i++)//输出排序前的数组
	{
		cout << a[i] << "\t";
	}
	cout << endl;
	paixu1(a, n);
	cout << "冒泡排序后的数组为：";
	for (int i = 0; i < n; i++)//输出排序后的数组
	{
		cout << a[i] << "\t";
	}
	//找到数组中第K大的数据
	int k;
	cout << "输入你想找的第几大的数据:";
	cin >> k;
	if (k > n)
	{
		return false;
	}
	else
	{
		cout << "第" << k << "大的数据为" << a[k-1] << endl;
	}


	cout << endl;
	cout << "上面为降序冒泡排序，时间复杂度为O(n^2),下面为基数升序排序，时间复杂度为o(n)" << endl;

	//基数升序排序（复杂度为o(n))
	int b[5] = { 1,11,59,36,3 };
	int z = sizeof(b) / sizeof(b[0]);
	cout << "基数排序前的数组为：";
	for (int i = 0; i < n; i++)//输出排序前的数组
	{
		cout << b[i] << "\t";
	}
	cout << endl;
	test01(b, z);
	paixu2(b, z);
	cout << "基数排序后的数组为：";
	for (int i = 0; i < n; i++)//输出排序后的数组
	{
		cout << b[i] << "\t";
	}
	//找到数组中第K大的数据
	int m;
	cout << "输入你想找的第几大的数据:";
	cin >> m;
	if (m > z)
	{
		return false;
	}
	else
	{
		cout << "第" << k << "大的数据为" << b[z-m] << endl;
	}

}